package com.linzm.leetcode.primary.exercises1_20230114;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author zimingl
 * @Date 2023/1/14 15:47
 * @Description: 人口最多的年份 90m 差分数组法
 *
 * 做法 List<int[]>、 stream sorted
 */
public class Demo6_1854 {
    /**
     * 输入：logs = [[1950,1961],[1960,1971],[1970,1981]]
     * 输出：1960
     * 解释：
     * 人口最多为 2 ，分别出现在 1960 和 1970 。
     * 其中最早年份是 1960 。
     */

    public static void main(String[] args) {
//        int[][] logs = {{1952,2006},{2021,2042},{2047,2049},{2036,2040},{1900,2009}, {1987,2047}};
        int[][] logs = {{1960, 1971}, {1970, 1981}, {1950, 1961}};
        // [[2033,2034],[2039,2047],[1998,2042],[2047,2048],[2025,2029],[2005,2044],[1990,1992],[1952,1956],[1984,2014]]
        // [[2017,2038],[2001,2013],[2032,2044],[1978,2031],[1950,1973],[2043,2045],[2028,2049],[1979,2042],[2037,2048],[2048,2049],
        // [1980,2021],[2047,2050],[1985,2014],[2028,2031],[1989,2009],[1956,1966],[2014,2043],[1993,2029],[1970,2036],[2013,2044]]
        Demo6_1854 demo6_1854 = new Demo6_1854();
        int yearNum = demo6_1854.maximumPopulation(logs);
        System.out.println(yearNum);
    }

    public int maximumPopulation(int[][] logs) {
        List<int[]> firstYearList = new ArrayList<>();
        List<int[]> secondYearList = new ArrayList<>();
        List<int[]> numYearList = new ArrayList<>();
        for (int i = 0; i < logs.length; i++) {
            int[] numYear = new int[2];
            numYear[0] = logs[i][0];
            numYear[1] = logs[i][1];
            firstYearList.add(numYear);
            secondYearList.add(numYear);
        }
        for (int[] first : firstYearList) {
            int[] numYear = new int[2];
            int count = 1;
            for (int[] second : secondYearList) {
                if (first[0] >= second[0] && first[0] < second[1]) {
                    count++;
                }
            }
            numYear[0] = first[0];
            numYear[1] = count;
            numYearList.add(numYear);
        }
        List<int[]> resListSorted = numYearList.stream()
                .sorted(Comparator.comparingInt(arr -> arr[0]))
                .sorted((arr1, arr2) -> arr2[1] - arr1[1])
                .collect(Collectors.toList());
        return resListSorted.get(0)[0];
    }

    public int maximumPopulation2(int[][] logs) {
        int offset = 1900;
        int[] peopleDealt= new int[200];
        // 统计
        for(int i = 0; i < logs.length; i++){
            peopleDealt[logs[i][0]-offset]++;
            peopleDealt[logs[i][1]-offset]--;
        }
        // 输出
        int peopleCount = 0, maxCount = 0, whichYear = 0;
        for(int i = 0; i < peopleDealt.length; i++){
            peopleCount += peopleDealt[i];
            if(peopleCount > maxCount){
                maxCount = peopleCount;
                whichYear = i + offset;
            }
        }
        return whichYear;
    }

    public int maximumPopulation3(int[][] logs) {
        Map<Integer, Integer> diff = new TreeMap<>();
        for(int[] a : logs) {
            diff.put(a[0], diff.getOrDefault(a[0], 0) + 1);
            diff.put(a[1], diff.getOrDefault(a[1], 0) - 1);
        }
        int ans = 0, cur = 0, cnt = 0;
        for(int k : diff.keySet()) {
            cnt += diff.get(k);
            if(cnt > cur) {
                ans = k; cur = cnt;
            }
        }
        return ans;
    }
}
